1. Technical Field
The present invention is directed to a manner in which a processing system schedules the running of threads and the like. More particularly, the invention is directed to a system having adaptive partition scheduling for process threads.
2. Related Art
The kernel of an operating system should be capable of dividing up CPU resources so that each thread that is active in the system obtains an adequate amount of CPU time to properly execute the corresponding process. To this end, the kernel may implement a scheduling system that determines how the available CPU time is allocated between multiple threads.
There are at least three types of process scheduling systems: a FIFO scheduling system; a round-robin scheduling system; and a sporadic scheduling system. In each system, a priority value is assigned to each thread of a process that is executed by the CPU. High priority values are assigned to threads that may be important to the operation of the overall system while threads that may be less important to the operation of the system have lower priority values. Whether the scheduling system gives a thread access to the CPU also depends on the state of the thread. For example, a thread may be ready or blocked (although other states also may be used). A thread is ready when it is capable of being executed in that all conditions needed for it to run have been met. In contrast, a thread is blocked when it tries to initiate an operation that cannot be completed immediately and must wait for the completion of some event before execution of the thread may continue.
In a FIFO scheduling system, the currently executing thread continues to use all of the CPU time until it gives up the CPU by blocking, it finishes execution, or it is preempted by a higher priority thread. Once one of these criterion are met, the FIFO scheduling system allocates the CPU to the highest priority process/thread that is in a ready state. Generally, there is one ready queue for each priority level.
A round-robin scheduling system uses an additional parameter, a timeslice, to allocate CPU time to a thread. A timeslice is an amount of time during which a thread is allowed to access the CPU. In a round-robin scheduling system, the currently executing thread continues to use all of the CPU time until the occurrence of one of the following events: 1) the currently executing process blocks; 2) the currently executing process finishes; 3) the currently executing process is preempted by a higher priority thread; or 4) the currently executing process uses up its timeslice. Once the currently executing process blocks or uses up its timeslice, it is put at the back of the ready queue for its priority level.
Sporadic scheduling is somewhat similar to round-robin scheduling. In a sporadic scheduling system, the currently executing process continues to use all of the CPU time until the occurrence of one of the following events: 1) the currently executing process blocks; 2) the currently executing process finishes; 3) the currently executing process is preempted by a higher priority thread; or 4) the currently executing process uses up a capped limit on the execution time assigned to the thread within a given period of time. The capped limit is known as a budget, while the given period of time in which this budget may be used is known as the replenishment period. In operation, the budget for a thread is replenished upon expiration of the replenishment period. Once the currently executing process blocks, it is put at the back of the ready queue for its priority level. However, if the currently executing process uses up its budget within the replenishment period, its priority level is reduced by a predetermined value and it is placed at the back of the ready queue for this lower priority level. The priority level of the process/thread may be returned to its original value in response to a number of different conditions.
In certain operating systems, such as those available from QNX Software Systems in Kanata, Ontario, each thread in the system may run using any of the foregoing scheduling systems. Consequently, the scheduling systems are effective on a per-thread basis for all threads and processes on a node. Each thread is assigned to a particular scheduling system type through the operation of the process/thread itself. This provides the software designer with a significant degree of design flexibility, but also involves a need for coordination between software designers implementing code for the same system. This coordination includes the assignment of priorities to the different threads as well as the scheduling system type assigned to each thread.
Some available operating systems apply scheduling on a global basis. One such global scheduling system is known as fair-share scheduling. In a fair-share scheduling system, CPU usage may be equally distributed among system users, groups, or processes. For example, if four users (A, B, C, D) are concurrently executing one process each, the fair-share scheduler will logically divide the available CPU cycles such that each user gets 25% of the whole (100%/4=25%). If user B starts a second process, each user will still receive 25% of the total cycles, but both of user B's processes will each receive 12.5% of the total available CPU time. On the other hand, if a new user starts a process on the system, the scheduler will reapportion the available CPU cycles such that each user gets 20% of the whole (100%/5=20%).
Another layer of abstraction allows partitioning of users into groups, and application of the fair share system to the groups as well. In this case, the available CPU cycles are divided first among the groups, then among the users within the groups, and then among the processes for that user. For example, if there are three groups (1, 2, 3) containing three, two, and four users respectively, the available CPU cycles may be distributed as follows: 100%/3 groups=33.3% per group Group 1: (33.3%/3 users)=11.1% per user Group 2: (33.3%/2 users)=16.7% per user Group 3: (33.3%/4 users)=8.3% per user. Other percentage distributions among the groups also may be used.
One manner of logically implementing fair-share scheduling strategy is to recursively apply a round-robin scheduling strategy at each level of abstraction (processes, users, groups, etc.). In round robin scheduling, threads of equal importance or priority take turns running. They each run for intervals, or timeslices, that are the property of each thread or group of threads.
While the foregoing scheduling systems have advantages in different applications, they may experience deficiencies when used in certain system applications. For example, when per-thread scheduling systems are used in real-time systems where the latencies of a process/thread have been planned solely through the assignment of priority levels, very long latencies for low-priority threads may occur. Malicious software processes may configure themselves for high priority execution and thereby preempt proper scheduling of lower priority threads. This problem also may occur, for example, during system development when a high priority thread malfunctions and enters an infinite loop. Global fair-share scheduling systems may avoid such problems, but lack the responsiveness needed for use in a real-time system. Therefore, a need exists for a scheduling system that may effectively allow high-priority threads to operate on a real-time basis while concurrently providing some sort of fair-share CPU access to all threads.